\section{Minimum Region Tracking and
Maximum Utility Assignment}
\label{sec:method}
In this section, we propose a Minimum tracking Region
and Maximum system Utility (MRMU) scheme,
which consists of two phases,
%i.e., \emph{offline object movement prediction}
%and \emph{online tracking task assignment},
to tackle the object tracking problem in Section~\ref{subsec:prob_state}.
First,
\emph{Offline object movement prediction} leverages
the historical dataset $D$
trains the offline Clustering representation-based $N$-Gram ($N$-Gram-C) movement prediction model.
%then
%utilize the observations (e.g., the trip to be discovered)
%to retrieve most probable travel of the object next time.
Second,
\emph{Online tracking task assignment}
formulate the optimal decision problem
as a maximum weighted bipartite matching (MWBM) problem,
and Kuhn-Munkres (KM) algorithm is utilized
to solve the MWBM problem.

\subsection{Offline object movement prediction}
\label{subsec:off_pred}
We employ a variant of the k-means clustering algorithm
to learn locations from $D$ like~\cite{ashbrook2002learning}.
As Fig.~\ref{fig:move_predict}(a)-(c) depicts,
the key idea is to cluster all SP to belonged circles,
the circle center is the mean of all SP within the circle.
Finally, we collect a set of means, namely locations,
and each GPS-based trajectory representation $Tr$
can be transformed to
location-based representation,
e.g., $Tr_1=\{l_2,l_3,l_1\}$.
We omit the timestamp for the GPS-collection interval
is often fixed (i.e., a time slot).

The core idea of $N$-Gram
is to split each trajectory to a sequence of $n$-size grams.
For example, for trajectory $Tr_1$ and
a 2-Gram model, after decomposition, it will be denoted as
$\{(l_2,l_3),(l_3,l_1)\}$.

Then the frequency of every gram
is counted by% using (\ref{eq:gram_fre_cnt}).
\begin{equation}\label{eq:gram_fre_cnt}
  p(l_{i-n+1},\ldots,l_i) = \frac{count(l_{i-n+1},\ldots,l_i)}{count(Allgram)}.
\end{equation}

%\begin{definition}[Gram]\label{def:Gram}
%A sequence of adjacent locations is called gram, e.g.,
%each pair of location builds a Bi-Gram.
%\end{definition}
Next, for a trajectory $Tr_i=\{l_{i1},l_{i2},\ldots,l_{ie}\}$,
its probability according to the chain rule is
given by
\begin{equation}\label{eq:tr_prob_cal}
  P(Tr_i)=p(l_{i1})\ast p(l_{i2}|l_{i1})\cdots
  p(l_{ie}|l_{i1},\ldots,l_{i(e-1)}).
\end{equation}

Applying the Markov Assumption and we can get
\begin{equation}\label{eq:markov}
  P(Tr_i)=\prod_{j=1}^eP(l_{ij}|l_{i(j-n+1)},\ldots,l_{i(j-1)}).
\end{equation}

$P(l_{ij}|l_{i(j-n+1)},\ldots,l_{i(j-1)})$
(denoted by $P_M(l_{ij})$)
can be obtained with maximum likelihood estimation
as follows:
\begin{equation}\label{eq:mle}
  P_M(l_{ij})=\frac{count(l_{ij}|l_{i(j-n+1)},\ldots,l_{ij})}{count(l_{ij}|l_{i(j-n+1)},\ldots,l_{i(j-1)})}.
\end{equation}

All grams' conditional probability will be produced
with (\ref{eq:mle}),
and a transition probability graph ($TPG$) would be formed,
namely, the N-Gram model has been constructed.
Fig.~\ref{fig:move_predict}(d) shows $TPG$
in the scenario of Fig.\ref{fig:move_predict}(a)
with a 2-gram model.

Once the ongoing trip of the object
is updated by workers,
and the tracking rate $P_\zeta$ is set,
The minimized sensing region
can be derived from (\ref{eq:markov}),
i.e., determines the minimal $k$ most probable future trips.

\subsection{Online Tracking Task Assignment}
\begin{figure}
%\vspace{-0.8cm}  %调整图片与上文的垂直距离
  \setlength{\abovecaptionskip}{0.1cm}   %调整图片标题与图距离
  \setlength{\belowcaptionskip}{-0.5cm}   %调整图片标题与下文距距离
\begin{minipage}{0.45\linewidth}
\centerline{\includegraphics[width=0.90\textwidth]{fig/original_assignment.pdf}}
\centerline{\small{(a) Original Strategy}}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\centerline{\includegraphics[width=0.90\textwidth]{fig/reformulation.pdf}}
\centerline{\small{(b) After Reformulation}}
\end{minipage}
\caption{An Example of Task Assignment.}
\label{fig:task_assign}
\end{figure}

According to the prediction result,
we define $k$ concurrent subtasks
for a tracking task $T$ as $T=\{s_1,s_2,\ldots,s_k\}$.
Each subtask requires a worker to take photos under
the time constraint given by
\begin{equation}\label{eq:time_ctr}
  \frac{dist(w_i,\hat{l})}{v_w}<\frac{dist(l_j,\hat{l})}{v_c},
\end{equation}
where $dist(w_i,\hat{l})$ is the distance
that workers need to move to sensing location $\hat{l}$,
$dist(l_j,\hat{l})$ is the distance between
the object and $\hat{l}$.
$v_w$ and $v_c$ are the average speed of
workers and the object, respectively.
(\ref{eq:time_ctr}) depicts an available assignment
must meet the requirement that
workers should arrive at the sensing locations
before the target.

To simplify the expressions, we define a bipartite graph
$G$$=<$$W,\hat{R},E$$>$, where $E$ denotes the set of possible
assignment. According to the definition of the optimal
decision problem in Section~\ref{sec:model}, one location
requires one worker, but there may be no worker fit the
time constraint to be assigned for a certain location,
or too many workers but fewer locations, as
Fig.\ref{fig:task_assign}(a) depicts.
Thus, we add dummy workers or locations to ensure
$|W|=|\hat{R}|$, and dummy impossible assignment,
which gains no utility, are added then.
In this way, the original bipartite graph $G$ can be extended
to a balanced and complete bipartite graph
$G'$$=<$$\mathcal{W},\mathcal{L},\mathcal{E}$$>$, which is shown in
Fig.\ref{fig:task_assign}(b). Finally, the optimal
decision problem (\ref{eq:optimal1}) is formulated as a
maximum weighted bipartite matching problem in $G'$ as
follows:
\begin{equation}
\label{eq:optimal2}
\begin{aligned}
  \max_\phi& \sum_{(w_i,l_j)\in\mathcal{E}}u(w_i,l_j)\cdot\phi(w_i,l_j),\\
  \text{s.t.}~~&
  \sum_{l_j}\phi(w_i,l_j)=1, \forall l_j\in \mathcal{L},\\
  ~&\sum_{w_i}\phi(w_i,l_j)=1, \forall w_i\in \mathcal{W},\\
  ~&\phi(w_i,l_j)\in \{0,1\}, \forall w_i\in\mathcal{W},l_j\in \mathcal{L}.
\end{aligned}
\end{equation}


\begin{algorithm}
  \setlength{\abovecaptionskip}{-0.5cm}   %调整图片标题与图距离
  \setlength{\belowcaptionskip}{-0.5cm}   %调整图片标题与下文距离
\caption{Minimum Region Maximum Utility Algorithm}
\label{alg:MinRMaxU}
\begin{small}
\begin{algorithmic}[1]
\REQUIRE $f(t),D,W,P_\zeta$.
\ENSURE Determine the minimum sensing region $\hat{R}$,
and find an optimal assignment $\phi_{opt}$
to maximize $U(T,t)$.
\renewcommand{\algorithmicrequire}
{\textbf{Phase1: \textit{Offline movement prediction}}}
\REQUIRE
\STATE {Initialize $L=\emptyset$, set $\mathbb{T},r,n$;}
\STATE {Filter out SP set $S$ from $D$ according to $\mathbb{T}$;}
\WHILE {$S$ is not empty}
    \STATE {Take a significant position $g$ from $S$, $g_m=(g.lat,g.lon)$;}
    \WHILE {True}
        \STATE {Collect SP set $S'$ within circle $(g_m,r)$;}
        \IF {$g_m=(mean(S'.lat),mean(S'.lon))$}
            \STATE {Break the current loop;}
        \ELSE
            \STATE{$g_m\leftarrow(mean(S'.lat),mean(S'.lon))$;}
        \ENDIF
    \ENDWHILE
    \STATE {$L\leftarrow L\cup g_m$;}
    \STATE {$S\leftarrow S\backslash S'$;}
\ENDWHILE
%\STATE {Transform $Tr$ representation
%from GPS-based to location-based;}
\STATE {Construct $N$-Gram model;}
\renewcommand{\algorithmicrequire}
{\textbf{Phase2: \textit{Online Task Assignment}}}
\REQUIRE
\STATE {Initialize $p=0,\hat{R}=\emptyset$, set $P_\zeta$;}
\WHILE {$p<P_\zeta$}
    \STATE {Predict the most probable arrival location $\hat{l}$ in $L\backslash\hat{R}$;}
    \STATE {$p\leftarrow p+p(\hat{l}|f(t))$;}
    \STATE {$\hat{R}\leftarrow \hat{R}\cup\hat{l}$;}
\ENDWHILE
\STATE {Formulate $G=<W,\hat{R},E>$ to $G'=<\mathcal{W},\mathcal{L},\mathcal{E}>$;}
\STATE {Conduct KM algorithm to find $\phi$;}
\RETURN {$\phi$.}
\end{algorithmic}
\end{small}
\end{algorithm}


In this paper, we conduct KM algorithm,
which was proposed by
Kuhn et al.~\cite{kuhn1955hungarian},
can efficiently solve the MWBM problem in $O(n^3)$,
where $n$ is the number of vertices in the bipartite graph,
to achieve our Maximum Utility Task Assignment (MUTA) algorithm, and search an optimal task assignment (OTA) strategy.

The overall MRMU algorithm is shown in Algorithm~\ref{alg:MinRMaxU}.
